public class DeleteAndEarn {
    // 删除并获得点数
    // https://leetcode.cn/problems/delete-and-earn/
    public int deleteAndEarn(int[] nums) {
        // 首先为什么这道题目会想到使用dp
        // 对于第i个数来说，有两种选择，选择和不选择
        // 如果当前元素不删除的话那么和就是 dp[i-2] + nums[i]*count[i]
        // 如果当前元素删除的话，那么和就是dp[i-1]
        int[] hash = new int[10001];
        int max = 0;
        for (int num : nums) {
            hash[num]++;
            max = Math.max(max, num);
        }
        int[] dp = new int[max+1];
        dp[1] = hash[1];
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + i*hash[i]);
        }
        return dp[max];
    }
}
